// HW6B - Lane Harris, Paul Flores, Ken Norton

import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Set;

public class PowerGrid {

  /**
   * Entry point for the Power Grid Planner.
   * 
   * @param args Command line args (unused).
   */
  public static void main(String[] args) {
    System.out.println("Welcome to the Power Grid Planner!\n");

    SimpleGraph start_graph = new SimpleGraph();
    SimpleGraph mst = new SimpleGraph();

    Hashtable start_graph_hashtable = GraphInput.LoadSimpleGraph(start_graph);

    if (start_graph_hashtable == null) {
      return;
    }

    System.out.println();

    double weight = getMinimumSpanningTree(start_graph, mst);

    displayGraph(mst);

    System.out.println("\nTotal cost to connect every city: $" + weight);
  }

  /**
   * Finds a minimum spanning tree of a graph. Assumes a connected, non-empty graph. 
   * Uses Prim's algorithm under the hood.
   * 
   * @param graph The graph to use.
   * @param mst The minimum spanning tree.
   * @return The total weight of the MST.
   */
  public static double getMinimumSpanningTree(SimpleGraph graph, SimpleGraph mst) {
    Set<String> vertices_in_mst = new HashSet<String>();
    BinaryHeap available_edges = new BinaryHeap();
    Hashtable<String, Vertex> hashtable = new Hashtable<String, Vertex>();

    Edge next_edge;
    Vertex new_vertex;
    Vertex old_vertex;

    double total_weight = 0.0;

    // Start with an arbitrary vertex
    Vertex v = graph.aVertex();

    vertices_in_mst.add((String) v.getName());

    new_vertex = mst.insertVertex(v.getData(), v.getName());
    hashtable.put((String) v.getName(), new_vertex);

    Iterator i = graph.incidentEdges(v);
    while (i.hasNext()) {
      available_edges.insert(new PrimEdge((Edge)i.next()));
    }

    // While we haven't included every vertex in the MST
    while (vertices_in_mst.size() < graph.numVertices()) {
      // Grab the next cheapest edge that connects us to a new vertex
      // Or throw away edges that are useless.
      do {
        try {
          // Have to use our wrapper for edges here
          PrimEdge tmp = (PrimEdge) available_edges.deleteMin();
          next_edge = tmp.getEdge();
        } catch (EmptyHeapException e) {
          // TODO Auto-generated catch block
          System.out.println("Error: Input graph is not connected!");
          return 0.0;
        }
      } while (vertices_in_mst.contains((String) next_edge.getFirstEndpoint().getName()) &&
               vertices_in_mst.contains((String) next_edge.getSecondEndpoint().getName()));

      // Add the edge and it's endpoint to the MST
      if (vertices_in_mst.contains(next_edge.getFirstEndpoint().getName())) {
        old_vertex = next_edge.getSecondEndpoint();
        new_vertex =
            mst.insertVertex(next_edge.getSecondEndpoint().getData(), next_edge
                .getSecondEndpoint().getName());
        mst.insertEdge(hashtable.get(next_edge.getFirstEndpoint().getName()), new_vertex,
                       next_edge.getData(), next_edge.getName());
        vertices_in_mst.add((String) new_vertex.getName());
        hashtable.put((String) new_vertex.getName(), new_vertex);
      } else {
        old_vertex = next_edge.getFirstEndpoint();
        new_vertex =
            mst.insertVertex(next_edge.getFirstEndpoint().getData(), next_edge
                .getFirstEndpoint().getName());
        mst.insertEdge(hashtable.get(next_edge.getSecondEndpoint().getName()), new_vertex,
                       next_edge.getData(), next_edge.getName());
        vertices_in_mst.add((String) new_vertex.getName());
        hashtable.put((String) new_vertex.getName(), new_vertex);
      }

      // Add all edges incident to the new vertex to the heap.
      // Any useless edges will be thrown out by deleteMin() above.
      i = graph.incidentEdges(old_vertex);
      while (i.hasNext()) {
        available_edges.insert(new PrimEdge((Edge)i.next()));
      }

      total_weight += (Double) next_edge.getData();
    }

    return total_weight;
  }

  /**
   * Displays a graph in terms of cities and powerlines.
   * @param graph The graph to display.
   */
  public static void displayGraph(SimpleGraph graph) {
    Iterator i;

    for (i = graph.vertices(); i.hasNext();) {
      Vertex v = (Vertex) i.next();
      System.out.println("City " + v.getName());
      Iterator j;

      for (j = graph.incidentEdges(v); j.hasNext();) {
        Edge e = (Edge) j.next();
        
        if (e.getFirstEndpoint().equals(v)) {
          System.out.println("  Powerline to " + e.getSecondEndpoint().getName() + " ($" +
                             (Double) e.getData() + ")");
        }
        else
        {
          System.out.println("  Powerline to " + e.getFirstEndpoint().getName() + " ($" +
              (Double) e.getData() + ")");
        }
      }
    }
  }
}
